{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Parenthesis String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkValidString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的括号字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含三种字符的字符串，支持的字符类型分别是 <code>'('</code>、<code>')'</code> 和 <code>'*'</code>。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 <code>true</code> 。</p>\n",
    "\n",
    "<p>有效字符串符合如下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>任何左括号 <code>'('</code>&nbsp;必须有相应的右括号 <code>')'</code>。</li>\n",
    "\t<li>任何右括号 <code>')'</code>&nbsp;必须有相应的左括号 <code>'('</code>&nbsp;。</li>\n",
    "\t<li>左括号 <code>'('</code> 必须在对应的右括号之前 <code>')'</code>。</li>\n",
    "\t<li><code>'*'</code>&nbsp;可以被视为单个右括号 <code>')'</code>&nbsp;，或单个左括号 <code>'('</code>&nbsp;，或一个空字符串。</li>\n",
    "\t<li>一个空字符串也被视为有效字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"()\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(*)\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(*))\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s[i]</code> 为 <code>'('</code>、<code>')'</code> 或 <code>'*'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-parenthesis-string](https://leetcode.cn/problems/valid-parenthesis-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-parenthesis-string](https://leetcode.cn/problems/valid-parenthesis-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"()\"', '\"(*)\"', '\"(*))\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "\n",
    "        freedom = 0\n",
    "        l = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                freedom+=1\n",
    "                l+=1\n",
    "            elif c == ')':\n",
    "                freedom-=1\n",
    "                if freedom < 0:\n",
    "                    return False\n",
    "                if l:\n",
    "                    l-=1                    \n",
    "            else:\n",
    "                freedom+=1\n",
    "                if l:\n",
    "                    l-=1\n",
    "        return not l\n",
    "\n",
    "        # freedom = 0\n",
    "        # l, r = 0, 0\n",
    "        # for c in s:\n",
    "        #     if c == '(':\n",
    "        #         l+=1\n",
    "        #     elif c == ')':\n",
    "        #         r+=1\n",
    "        #     else:\n",
    "        #         freedom+=1\n",
    "        #     if l<r:\n",
    "        #         freedom-=1\n",
    "        #         l+=1\n",
    "        #         if freedom < 0:\n",
    "        #             return False\n",
    "        # freedom = 0\n",
    "        # l, r = 0, 0\n",
    "        # for c in reversed(s):\n",
    "        #     if c == '(':\n",
    "        #         l+=1\n",
    "        #     elif c == ')':\n",
    "        #         r+=1\n",
    "        #     else:\n",
    "        #         freedom+=1\n",
    "        #     if r<l:\n",
    "        #         freedom-=1\n",
    "        #         r+=1\n",
    "        #         if freedom < 0:\n",
    "        #             return False\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack_1=[]\n",
    "        stack_2=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==\"(\":\n",
    "                stack_1.append(\"(\")\n",
    "            if s[i]==\")\":\n",
    "                if len(stack_1)!=0:\n",
    "                    stack_1.pop()\n",
    "                else:\n",
    "                    if len(stack_2)!=0:\n",
    "                        stack_2.pop()\n",
    "                    else:\n",
    "                        return False\n",
    "            if s[i]==\"*\":\n",
    "                stack_2.append(s[i])\n",
    "        stack_1[:]=[]\n",
    "        stack_2[:]=[]\n",
    "        for i in range(len(s)):\n",
    "            idx=len(s)-i-1\n",
    "            if s[idx]==\")\":\n",
    "                stack_1.append(\")\")\n",
    "            if s[idx]==\"(\":\n",
    "                if len(stack_1)!=0:\n",
    "                    stack_1.pop()\n",
    "                else:\n",
    "                    if len(stack_2)!=0:\n",
    "                        stack_2.pop()\n",
    "                    else:\n",
    "                        return False\n",
    "            if s[idx]==\"*\":\n",
    "                stack_2.append(\"*\")\n",
    "        return True\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        st = set([0])\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                st = set(map(lambda x: x + 1, st))\n",
    "            elif c == ')':\n",
    "                st = set(map(lambda x: x - 1, filter(lambda x: x > 0, st)))\n",
    "            else:\n",
    "                i = set(map(lambda x: x + 1, st))\n",
    "                j = set(map(lambda x: x - 1, filter(lambda x: x > 0, st)))\n",
    "                st = st | i | j\n",
    "            #print(st)\n",
    "            if len(st) == 0:\n",
    "                return False\n",
    "        return 0 in st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        old_set = set([0])\n",
    "        for c in s:\n",
    "            new_set = set()\n",
    "            if c == '(':\n",
    "                for t in old_set:\n",
    "                    new_set.add(t + 1)\n",
    "            elif c == ')':\n",
    "                for t in old_set:\n",
    "                    if t > 0:\n",
    "                        new_set.add(t - 1)\n",
    "            elif c == '*':\n",
    "                for t in old_set:\n",
    "                    new_set.add(t + 1)\n",
    "                    new_set.add(t)\n",
    "                    if t > 0:\n",
    "                        new_set.add(t - 1)\n",
    "            old_set = new_set\n",
    "        return 0 in old_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Stack:  \n",
    "    \"\"\"模拟栈\"\"\"  \n",
    "    def __init__(self):  \n",
    "        self.items = []  \n",
    "          \n",
    "    def isEmpty(self):  \n",
    "        return len(self.items)==0   \n",
    "      \n",
    "    def push(self, item):  \n",
    "        self.items.append(item)  \n",
    "    \n",
    "    def pop(self):  \n",
    "        return self.items.pop()   \n",
    "      \n",
    "    def top(self):  \n",
    "        if not self.isEmpty():  \n",
    "            return self.items[len(self.items)-1]  \n",
    "          \n",
    "    def size(self):  \n",
    "        return len(self.items)   \n",
    "    \n",
    "class Solution:\n",
    "    def checkValidString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        '''\n",
    "        ((())*)*)\n",
    "        1.两个栈：左括号和*\n",
    "        2.先是右括号与两个栈匹配，之前的左括号够用，就pop出来；不够用就将*pop出来，作为(\n",
    "        3.右括号没有了，就拿左括号和*匹配,但左括号序数必须在*前面；左括号empty就OK了,左括号没有empty就是false\n",
    "        '''\n",
    "        leftP=Stack()\n",
    "        starP=Stack()\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='(':\n",
    "                leftP.push({'(':i})\n",
    "            elif s[i]=='*':\n",
    "                starP.push({'*':i})\n",
    "            else:\n",
    "                if leftP.size()>0:\n",
    "                    leftP.pop()\n",
    "                elif starP.size()>0:\n",
    "                    starP.pop()\n",
    "                else:\n",
    "                    return False\n",
    "        while leftP.isEmpty()==False and starP.isEmpty()==False:\n",
    "            if leftP.top()[\"(\"]>starP.top()[\"*\"]:\n",
    "                return False\n",
    "            leftP.pop()\n",
    "            starP.pop()\n",
    "        return leftP.isEmpty()\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n1, n2 = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                n1 += 1\n",
    "            elif c == ')':\n",
    "                if n1 > 0:\n",
    "                    n1 -= 1\n",
    "                elif n2 > 0:\n",
    "                    n2 -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                n2 += 1\n",
    "        n1, n2 = 0, 0\n",
    "        for c in s[::-1]:\n",
    "            if c == ')':\n",
    "                n1 += 1\n",
    "            elif c == '(':\n",
    "                if n1 > 0:\n",
    "                    n1 -= 1\n",
    "                elif n2 > 0:\n",
    "                    n2 -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                n2 += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        L, R = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ')':\n",
    "                L += 1\n",
    "                if i + 1 - L < L:\n",
    "                    return False\n",
    "            if s[-i - 1] == '(':\n",
    "                R += 1\n",
    "                if i + 1 - R < R:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        lb,rb=0,0\n",
    "        for c in s:\n",
    "            # print(lb,rb)\n",
    "            if c=='(':\n",
    "                rb+=1\n",
    "                lb+=1\n",
    "            elif c==')':\n",
    "                if lb>0:\n",
    "                    lb-=1\n",
    "                if rb>0:\n",
    "                    rb-=1\n",
    "                else:\n",
    "                    return False\n",
    "            elif c=='*':\n",
    "                if lb>0:\n",
    "                    lb-=1\n",
    "                rb+=1\n",
    "            \n",
    "            if rb<0:\n",
    "                return False\n",
    "        if lb<=0<=rb:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        left = []\n",
    "        xing = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                left.append(i)\n",
    "            elif s[i] == ')':\n",
    "                if left:\n",
    "                    left.pop(-1)\n",
    "                elif xing:\n",
    "                    xing.pop(-1)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                xing.append(i)\n",
    "        if len(left) > len(xing):\n",
    "            return False\n",
    "        else:\n",
    "            for leftidx in reversed(left):\n",
    "                if leftidx > xing.pop(-1):\n",
    "                    return False\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        L, R = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ')':\n",
    "                L += 1\n",
    "                if i + 1 - L < L:\n",
    "                    return False\n",
    "            if s[-i - 1] == '(':\n",
    "                R += 1\n",
    "                if i + 1 - R < R:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        if s is None:\n",
    "            return False\n",
    "        \n",
    "        if len(s) == 0:\n",
    "            return True\n",
    "        \n",
    "        stack0 = []\n",
    "        stack1 = []\n",
    "        for index, char in enumerate(s):\n",
    "            if char == '*':\n",
    "                stack0.append(index)            \n",
    "            elif char == '(':\n",
    "                stack1.append(index)\n",
    "            elif char == ')':                    \n",
    "                if len(stack1) > 0:\n",
    "                    stack1.pop()\n",
    "                elif len(stack0) > 0:\n",
    "                    stack0.pop()\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        if len(stack1) == 0:\n",
    "            return True\n",
    "\n",
    "        while len(stack1) > 0:\n",
    "            if len(stack0) == 0:\n",
    "                return False\n",
    "            \n",
    "            if stack0[-1] < stack1[-1]:\n",
    "                return False\n",
    "            \n",
    "            stack0.pop()\n",
    "            stack1.pop()\n",
    "        \n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        lo=0\n",
    "        hi=0\n",
    "        for c in s:\n",
    "            if c=='(':\n",
    "                lo+=1\n",
    "                hi+=1\n",
    "            elif c=='*':\n",
    "                if lo>0:lo-=1\n",
    "                hi+=1\n",
    "            else:\n",
    "                if lo>0:lo-=1\n",
    "                hi-=1\n",
    "            if hi<0:\n",
    "                return False\n",
    "        return lo==0\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        if not s:\n",
    "            return True\n",
    "        left = []\n",
    "        asterisk = []\n",
    "        for symbol in s:\n",
    "            if symbol is \"(\":\n",
    "                left.append(symbol)\n",
    "            elif symbol is \"*\":\n",
    "                asterisk.append(symbol)\n",
    "            else:\n",
    "                if left:\n",
    "                    left.pop()\n",
    "                elif asterisk:\n",
    "                    asterisk.pop()\n",
    "                else:\n",
    "                    return False \n",
    "\n",
    "        left = []\n",
    "        asterisk = []\n",
    "        for symbol in s[::-1]:\n",
    "            if symbol is \")\":\n",
    "                left.append(symbol)\n",
    "            elif symbol is \"*\":\n",
    "                asterisk.append(symbol)\n",
    "            else:\n",
    "                if left:\n",
    "                    left.pop()\n",
    "                elif asterisk:\n",
    "                    asterisk.pop()\n",
    "                else:\n",
    "                    return False                                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        star = []\n",
    "        tmp = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                tmp.append(i)\n",
    "            elif s[i] == ')' and tmp != []:\n",
    "                tmp.pop()\n",
    "            elif s[i] == ')' and tmp == []:\n",
    "                if star != []:\n",
    "                    star.pop()\n",
    "                else:\n",
    "                    return False\n",
    "            elif s[i] == '*' :\n",
    "                star.append(i)\n",
    "        # print(star)\n",
    "        # print(tmp)\n",
    "        if len(tmp) == 0 : return True\n",
    "        elif len(tmp) > 0 and star != []:\n",
    "            for j in range(len(tmp)) :\n",
    "                for k in range(len(star)):\n",
    "                    if star[k] > tmp[j]:\n",
    "                        star[k] = 0\n",
    "                        tmp[j] = 0\n",
    "                        break\n",
    "\n",
    "            if sum(tmp)== 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        l_list = list()\n",
    "        s_list = list()\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            if c == '(':\n",
    "                l_list.append(i)\n",
    "            elif c == '*':\n",
    "                s_list.append(i)\n",
    "            elif c == ')':\n",
    "                if len(l_list) > 0:\n",
    "                    l_list.pop(-1)\n",
    "                elif len(s_list) > 0:\n",
    "                    s_list.pop(0)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        print(l_list, s_list)\n",
    "        for i in range(len(l_list)):\n",
    "            found = None\n",
    "            for j in range(len(s_list)):\n",
    "                if l_list[i] < s_list[j]:\n",
    "                    found = j\n",
    "                    break\n",
    "            if found is not None:\n",
    "                s_list.pop(found)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        # case 1: L(LLLRRR)R\n",
    "        # case 2: L...RL...R\n",
    "        n = len(s)\n",
    "        if n==0: return True\n",
    "        f = [[False] * n for _ in range(n)] # f[i][j] from i to j is valid or not\n",
    "        # corner case length = 1\n",
    "        for i in range(n):\n",
    "            if s[i]=='*':\n",
    "                f[i][i] = True\n",
    "        for l in range(2,n+1):\n",
    "            for i in range(0,n-l+1):\n",
    "                j = i+l-1\n",
    "                # case 1\n",
    "                if s[i] in '(*' and s[j] in '*)':\n",
    "                    if l == 2 or  f[i+1][j-1]:\n",
    "                        f[i][j] = True\n",
    "                        continue\n",
    "                # case 2\n",
    "                for k in range(i,j):\n",
    "                    if f[i][k] and f[k+1][j]:\n",
    "                        f[i][j] = True\n",
    "                        break\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def helper(left_nums, idx):\n",
    "            if idx == len(s):\n",
    "                return left_nums == 0\n",
    "            \n",
    "            if s[idx] == \"(\":\n",
    "                return helper(left_nums + 1, idx + 1)\n",
    "            elif s[idx] == \")\":\n",
    "                if not left_nums:\n",
    "                    return False\n",
    "                return helper(left_nums - 1, idx + 1)\n",
    "            else:\n",
    "                flag = helper(left_nums + 1, idx + 1) | helper(left_nums, idx + 1)\n",
    "                if left_nums:\n",
    "                    flag |= helper(left_nums-1, idx + 1)\n",
    "                return flag\n",
    "        \n",
    "        return helper(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "\n",
    "        stack = 0\n",
    "        dp = {}\n",
    "        def f(stack, input_s):\n",
    "            if input_s == \"\":\n",
    "                return stack == 0\n",
    "\n",
    "            if (stack, input_s) in dp:\n",
    "                return dp[(stack, input_s)]\n",
    "            \n",
    "            if input_s[0] == \")\":\n",
    "                if stack:\n",
    "                    dp[(stack, input_s)] = f(stack-1, input_s[1:])\n",
    "                    return dp[(stack, input_s)]\n",
    "                else:\n",
    "                    dp[(stack, input_s)] = False\n",
    "                    return False\n",
    "            elif input_s[0] == \"(\":\n",
    "                dp[(stack, input_s)] = f(stack+1, input_s[1:])\n",
    "                return dp[(stack, input_s)]\n",
    "            else:\n",
    "                \n",
    "                a1 = f(stack+1, input_s[1:])\n",
    "                if a1:\n",
    "                    dp[(stack, input_s)] = True\n",
    "                    return True\n",
    "                a2 = f(stack, input_s[1:])\n",
    "                if a2:\n",
    "                    dp[(stack, input_s)] = True\n",
    "                    return True\n",
    "                if stack and f(stack-1, input_s[1:]):\n",
    "                    dp[(stack, input_s)] = True\n",
    "                    return True\n",
    "                dp[(stack, input_s)] = False\n",
    "                return False\n",
    "\n",
    "        return f(0, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        left_min, left_max = 0, 0\n",
    "        for t in s:\n",
    "            if t == '(':\n",
    "                left_min += 1\n",
    "                left_max += 1\n",
    "            elif t == ')':\n",
    "                left_min = max(left_min - 1, 0)\n",
    "                left_max -= 1\n",
    "                if left_max < 0:\n",
    "                    return False\n",
    "            else:\n",
    "                left_min = max(left_min - 1, 0)\n",
    "                left_max += 1\n",
    "        return left_min == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        \"\"\"\n",
    "        贪心：维护未匹配的左括号的最小值和最大值（分别来处理*作为右括号和左括号的情况  *作为右括号 说明未匹配左括号-1）\n",
    "        当遇到左括号 最大最小均+1 遇到右括号 均-1\n",
    "        遇上*号 最小-1 最大+1\n",
    "        在任何时候 未匹配的数量都必须非负数\n",
    "        当最大值为负数时 说明没有左括号可以和它匹配了 直接返回false\n",
    "        当最小时为0时 不能继续减少了 保证它是非负的\n",
    "        遍历结束 最小值为0 则匹配成功 因为匹配失败会通过之前对最大值的判断来提前终止\n",
    "        \"\"\"\n",
    "        minCount,maxCount = 0,0\n",
    "        for c in s:\n",
    "            if c=='(':\n",
    "                minCount += 1\n",
    "                maxCount += 1\n",
    "            elif c==')':\n",
    "                minCount = minCount-1 if minCount>=1 else minCount\n",
    "                maxCount -= 1\n",
    "            else:\n",
    "                minCount = minCount-1 if minCount>=1 else minCount\n",
    "                maxCount += 1\n",
    "            if maxCount<0:\n",
    "                return False\n",
    "        return minCount==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        stack1 = deque([])\n",
    "        stack2 = deque([])\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='(':\n",
    "                stack1.append(i)\n",
    "            elif s[i]=='*':\n",
    "                stack2.append(i)\n",
    "            else:\n",
    "                if stack1:\n",
    "                    stack1.pop()\n",
    "                elif stack2:\n",
    "                    stack2.pop()\n",
    "                else:\n",
    "                    return False\n",
    "        if not stack1:\n",
    "            return True\n",
    "        else:\n",
    "            while stack1 and stack2:\n",
    "                ind = stack1.pop()\n",
    "                ind2 = stack2.pop()\n",
    "                if ind>ind2:\n",
    "                    return False\n",
    "            if not stack1:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def checkValidString(self, s: str) -> bool:\n",
    "#         stack_l = []\n",
    "#         stack_s = []\n",
    "#         stack_r = []\n",
    "#         for i in range(len(s)):\n",
    "#             if s[i] == '(':\n",
    "#                 stack_l.append(i)\n",
    "#             elif s[i] == ')':\n",
    "#                 if len(stack_l) != 0:\n",
    "#                     stack_l.pop()\n",
    "#                 else:\n",
    "#                     stack_r.append(i)\n",
    "#             else:\n",
    "#                 stack_s.append(i)\n",
    "\n",
    "\n",
    "        \n",
    "#         while len(stack_l) != 0 and len(stack_s)!= 0:\n",
    "#             if stack_l[-1] < stack_s[-1]:\n",
    "#                 stack_l.pop()\n",
    "#                 stack_s.pop()\n",
    "#             else: break\n",
    "#         if len(stack_l) != 0:\n",
    "#             return False\n",
    "        \n",
    "#         while len(stack_r) != 0 and len(stack_s) != 0:\n",
    "#             if stack_s[0] < stack_r[0]:\n",
    "#                 del stack_s[0]\n",
    "#                 del stack_r[0]\n",
    "#             else:\n",
    "#                 break\n",
    "#         if len(stack_r) != 0:\n",
    "#             return False\n",
    "        \n",
    "#         return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        dp = [[False for _ in range(len(s))]for _ in range(len(s))]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                dp[i][i] = True\n",
    "        \n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i:i+2] == '()' or s[i:i+2] == '(*' or s[i:i+2] == '*)' or s[i:i+2] == '**':\n",
    "                dp[i][i + 1] = True\n",
    "\n",
    "        for i in range(len(s) - 3, -1, -1):\n",
    "            for j in range(i + 2, len(s)):\n",
    "                if (s[i] == '(' and s[j] == ')') or (s[i] == '*' and s[j] == ')') or (s[i] == '(' and s[j] == '*') or (s[i] == '*' and s[j] == '*'):\n",
    "                    dp[i][j] =dp[i + 1][j - 1]\n",
    "                for k in range(i, j):\n",
    "                    if dp[i][k] and dp[k + 1][j] and not dp[i][j]:\n",
    "                        dp[i][j] = True\n",
    "\n",
    "        return dp[0][-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        if '(' not in s and ')' not in s:\n",
    "            return True\n",
    "        n = len(s)\n",
    "        p = ((\"(\", \")\"), (\"(\", \"*\"), (\"*\", \")\"), (\"*\", \"*\"))\n",
    "        # dp[i][j] 表示从 i 至 j 的元素是否为有效字符串\n",
    "        dp = [[False]*(n) for _ in range(n)]\n",
    "        for idx, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                dp[idx][idx] = True\n",
    "            if idx >= 1 and (s[idx-1], s[idx]) in p:\n",
    "                dp[idx-1][idx] = True\n",
    "        for l in range(2, n):\n",
    "            for i in range(n-l):\n",
    "                dp[i][i+l] = dp[i+1][i+l-1] & bool((s[i], s[i+l]) in p)\n",
    "                if not dp[i][i+l]:\n",
    "                    for k in range(i, i+l+1):\n",
    "                        if dp[i][k] and dp[k+1][i+l]:\n",
    "                            dp[i][i+l] = True\n",
    "                            break\n",
    "        return dp[0][n-1]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "\n",
    "        dp = []\n",
    "        dp.append(set([0]))\n",
    "        for i in s:\n",
    "            last_heights = dp[-1]\n",
    "            new_heights = set()\n",
    "            if i == '(':\n",
    "                for h in last_heights:\n",
    "                    new_heights.add(h+1)\n",
    "            elif i == ')':\n",
    "                for h in last_heights:\n",
    "                    if h-1 >= 0:\n",
    "                        new_heights.add(h-1)\n",
    "            elif i == '*':\n",
    "                for h in last_heights:\n",
    "                    new_heights.add(h+1)\n",
    "                    new_heights.add(h)\n",
    "                    if h-1 >= 0:\n",
    "                        new_heights.add(h-1)\n",
    "            dp.append(new_heights)\n",
    "        \n",
    "        return 0 in dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        stack_left,stack_star = [],[]\n",
    "        for i in range(len(s)):\n",
    "            # 左括号//星号 都分别入栈\n",
    "            if s[i] == '(':\n",
    "                stack_left.append(i)\n",
    "            elif s[i] == '*':\n",
    "                stack_star.append(i)\n",
    "            \n",
    "            # 如果遇到右括号\n",
    "            elif s[i] == ')':\n",
    "                # 如果有尚未匹配左括号 先与栈顶的左括号匹配\n",
    "                if stack_left:\n",
    "                    stack_left.pop()\n",
    "                # 否则、如果有尚未消耗的星号 则变身左括号与s[i]匹配 (出栈)\n",
    "                elif stack_star:\n",
    "                    stack_star.pop()\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        while stack_left:\n",
    "            if not stack_star:\n",
    "                return False\n",
    "            elif stack_left[-1]>stack_star[-1]:\n",
    "                return False\n",
    "            else:\n",
    "                stack_left.pop()\n",
    "                stack_star.pop()\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        o = c = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == '(' or s[i] == '*':\n",
    "                o += 1\n",
    "            else:\n",
    "                o -= 1\n",
    "            if o < 0:\n",
    "                return False\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == ')' or s[i] == '*':\n",
    "                c += 1\n",
    "            else:\n",
    "                c -= 1\n",
    "            if c < 0:\n",
    "                return False\n",
    "\n",
    "        return o >= 0 and c >= 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidString(self, s: str) -> bool:\n",
    "        left_stk, star_stk = [], []\n",
    "        for idx, val in enumerate(s):\n",
    "            if val == \"(\":\n",
    "                left_stk.append(idx)\n",
    "            elif val == \"*\":\n",
    "                star_stk.append(idx)\n",
    "            elif val == \")\":\n",
    "                if left_stk:\n",
    "                    left_stk.pop()\n",
    "                elif not left_stk and star_stk:\n",
    "                    star_stk.pop()\n",
    "                # left和star栈都为空\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        while left_stk and star_stk:\n",
    "            if left_stk[-1] > star_stk[-1]:\n",
    "                return False\n",
    "            else:\n",
    "                left_stk.pop()\n",
    "                star_stk.pop()\n",
    "        \n",
    "        # left栈为空，则返回真；\n",
    "        return True if not left_stk else False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
